package leetbook.sort_search;

/**
 *  寻找峰值，-1和n位置的数被认为是-∞
 *  峰值找到一个即可
 *  思路：二分查找
 *  若mid位置递减，说明[0,mid]中有峰值
 *  若mid位置递增，说明[mid+1,n-1]中有峰值
 *  此外：边界处理后，该问题与Solution852类似
 */
public class Solution162 {

    public static void main(String[] args) {

        int[] nums = {6,5,4,3,2,3,2};
        System.out.println(new Solution162().findPeakElement(nums));

    }

    public int findPeakElement(int[] nums) {
        // TODO: 2021/8/5 边界处理好后，更容易理解
        int n = nums.length, l = 0, r = n - 1, mid = 0;
        while (l<=r){
            mid = (l+r)>>1;
            if(mid<n-1&&nums[mid]<nums[mid+1]){ //mid单增
                l = mid + 1;
            }else if(mid<n-1&&mid>0&&nums[mid]>nums[mid+1]&&nums[mid-1]>nums[mid]){ //mid单减但不是极值
                r = mid - 1;
            }else { //mid单减而且是极值
                return mid;
            }
        }
        return r+1;
    }
}
